package msb.class02;


import org.junit.Assert;
import org.junit.Test;
import common.pojo.LinkedNode;
import common.util.ArrayUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 单向链表翻转
 */
public class Code01_ReverseSinglyLinked {

    public static LinkedNode reverse(LinkedNode head) {
        LinkedNode current = head;
        LinkedNode pre = null;
        LinkedNode next;
        while (current != null) {
            next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }

    public static LinkedNode instance() {
        LinkedNode next = null;
        for (int i = 0; i < 50; i++) {
            LinkedNode node = new LinkedNode();
            node.value = ArrayUtil.randomInt(0, 100);
            node.next = next;
            next = node;
        }
        return next;
    }

    public static LinkedNode copy(LinkedNode head) {
        List<LinkedNode> list = transList(head);
        List<LinkedNode> copy = new ArrayList<>();

        for (int i = 0; i < list.size(); i++) {
            LinkedNode node = new LinkedNode();
            node.value = list.get(i).value;
            copy.add(node);
        }

        for (int i = 0; i < list.size() - 1; i++) {
            copy.get(i).next = copy.get(i + 1);
        }
        return copy.get(0);
    }

    public static List<LinkedNode> transList(LinkedNode head) {
        ArrayList<LinkedNode> list = new ArrayList<>();
        LinkedNode current = head;
        while (current != null) {
            list.add(current);
            current = current.next;
        }
        return list;
    }

    public static LinkedNode reverseCompare(LinkedNode head) {
        List<LinkedNode> list = transList(head);
        for (int i = list.size() - 1; i >= 0; i--) {
            LinkedNode next;
            if (i == 0) {
                next = null;
            } else {
                next = list.get(i - 1);
            }
            list.get(i).next = next;
        }
        return list.get(list.size() - 1);
    }


    @Test
    public void check() {
        for (int i = 0; i < 10000; i++) {
            LinkedNode instance = instance();
            LinkedNode instanceCompare = copy(instance);

            LinkedNode tail = reverse(instance);
            LinkedNode current = tail;

            LinkedNode tailCompare = reverseCompare(instanceCompare);
            LinkedNode currentCompare = tailCompare;

            while (current != null || currentCompare != null) {
                Assert.assertEquals(currentCompare.value, current.value);
                current = current.next;
                currentCompare = currentCompare.next;
            }
        }
    }

}
